Basic Category Theory for Computer Scientists §1.6 - §1.10
擔當ne-sachirou.icon
universal construction (普遍 (圈論)的構成) 何らかの property (性質) を持った object (對象) と arraow (射) の類 (class)を考へる cf. §1.5 Products
$ A \times B,$ A,B,A \times B \in|{\bf C}|を構成する
圖式$ A\xleftarrow{x_1}X\xrightarrow{x_2}B,$ X \in |{\bf C}|を考へる
§1.5 では$ (C,f,g)と$ (A \times B,\pi_1,\pi_2)
圖式$ A\xleftarrow{x_1}X\xrightarrow{x_2}Bは「A と B への wedge の圈 (以下 wedge の圈)」の對象である
wedge の圈の射$ m:(A\xleftarrow{w_1}W\xrightarrow{w_2}B) \to (A\xleftarrow{x_1}X\xrightarrow{x_2}B)には、可換圖式$ W\xrightarrow{m}X\xrightarrow{x_1}A\xleftarrow{w_1}W\xrightarrow{w_2}B\xleftarrow{x_2}X\xleftarrow{m}Wを滿たす射$ m\in{\rm Hom}_{\bf C}:W\to Xを當てる $ w_1=m;x_1 ,$ w_2=m;x_2
wedge の圈の終對象$ A\xleftarrow{p_1}P\xrightarrow{p_2}B この$ Pを$ A \times Bと書く。つまり積 (圈)である 普遍 (圈論)的に構成されたものは、もし存在すれば同型を除いて一意に決まる meditating arrow (仲介射。meditating map)
unique (存在してしかも一意。ただ1つ存在する)
co-universal construction (餘普遍的構成) §1.5 では coproduct (餘積。和) が餘普遍的に構成されてゐる 餘普遍的に構成されたものは、もし存在すれば同型を除いて一意に決まる §1.7.1 定義
射$ e:X\to Aが射$ f,g:A\to Bの等化子であるとは 可換圖式$ X\xrightarrow{e}A\xrightarrow{f,g}B。$ e;f=e;g $ e';f=e';gを滿たすどんな$ e':X'\to Aに對しても、$ k;e=e'を滿たす射$ k:X'\to Xが存在してしかも一意 (普遍 (圈論)性) つまり可換圖式$ B\xleftarrow{f,g}A\xleftarrow{e}X\xleftarrow{\exist!k}X'\xrightarrow{e'}A\xrightarrow{f,g}B §1.7.2 練習問題
射$ f,g:A \to Bが在る時
$ e;f=e;gを滿たす射$ e:X \to Aを考へる
つまり圖式$ X\xrightarrow{e}A\xrightarrow{f,g}Bを考へる
對象は組$ (X,e)
射$ k:(X',e') \to (X,e)は、可換圖式$ B\xleftarrow{f,g}A\xleftarrow{e}X\xleftarrow{k}X'\xrightarrow{e'}A\xrightarrow{f,g}Bを滿たす射$ k:X'\to X 等化子$ (X,e)は終對象$ \forall (X',e')\exist! k_{:(X',e')\to(X,e)} §1.7.3 例
2 つの寫像 ($ \bf Setでの射)$ f,g:A \to B
集合$ X \subseteq A,$ X:=\{x|x\in A,f(x)=g(x)\} 寫像$ e:X \to A,$ e:x\mapsto x
$ f \circ e(x)=f(x)=g(x)=g \circ e (x)である
$ f \circ e'=g \circ e'を滿たす$ e':X' \to Aを考へる
$ \exist k_{:X'\to X}(e\circ k=e').
$ \because$ Xの定義より、$ f \circ e'=g \circ e'である爲には$ {\rm cod}(e')=X={\rm dom}(e)である。よって$ k:=e'と定義すれば$ \exist e'\implies\exist k
$ \forall k,k'_{:X' \to X}(e \circ k=e \circ k'=e'\implies k=k').
$ \because$ e \circ k=e \circ k'であり$ eは恆等寫像なので$ k=k'
寫像$ e:B \to Xが寫像$ f,g:A \to Bの餘等化子であるとは $ e \circ f=e \circ gである
$ e' \circ f=e' \circ gを滿たすどんな$ e':B \to X'に對しても$ \exist!k_{:X\to X}
集合の圈において、二つの寫像$ f,g:X\to Yの餘等化子は、$ \forall x_{\in X}(f(x)\sim g(x)) を滿たす最小の同値關係$ \simによる$ Yの商である。特に$ Rが集合$ Y上の同値關係で、その各成分への射影$ r_1,r_2:R_{\subset X\times Y}\to Yを取れば、$ r_1,$ r_2の餘等化子は商集合$ Y/Rにちょうど一致する。 $ y \sim y。$ f(x) \neq g(x)ならばこれらを$ f(x) \sim g(x)とする。$ y \in a \in Y/\simならば$ e(y)=aとすると$ eは餘等化子 §1.7.4 練習問題
poset (半順序、partially ordered set) を圈と見做した時、等化子はただ恆等射だけである事を示せ 半順序集合$ Pにおいて、對象は$ p,q,r \in P、射は$ p \le q、合成射は推移律$ p \le q \le r \to p \le r、恆等射は反射律$ p \le p $ \forall p,q_{\in P}\exist! f_{:p\le q}.
$ f,g:q \le rを考へる
$ f=gとなる
$ f=gであるから$ \forall p_{\le q}\exist e(f\circ e=g\circ e)
$ {\rm id}:q\le qは勿論$ f\circ id=g\circ id
$ \forall p_{\le q}\exist! e'_{:p\le q}.
$ f,g:q \le rについて$ \rm idでない等化子$ e:p<qが在るとする $ f\circ{\rm id}=g\circ{\rm id}であるから$ k:q\le pが存在しなければならない。しかし半順序集合であるからこれは存在しない ($ \because反對稱律$ a\le b\wedge b\le a\implies a=b) $ \therefore$ \rm idでなければ等化子ではない $ e \circ k=e \circ k'ならば射$ k,$ k'は仲介射であり、$ k=k'
等化子が epic (epi 射) であるならば、isomorphism (同型射) でもある事を示せ 等化子$ e:X \to Aが epi 射であるなら、$ f \circ e=g \circ e\implies f=g 射$ eが射$ f,$ gの等化子であるならば$ f=g $ f=g\implies f\circ{\rm id}_A=g\circ{\rm id}_Aであるから、仲介射$ k_A:A\to Xが存在する
射$ eが等化子であるから仲介射$ k_X:X \to Xが存在してしかも一意である 圈の公理より$ \exist{\rm id}_Xであるから$ k_X={\rm id}_x
圈の公理より$ \exist e \circ k_Aであり、また上記より$ {\rm dom}(h)={\rm cod}(h)=Xである射は$ {\rm id}_Xのみであるから、から$ e\circ k_A={\rm id}_X
$ \therefore$ k_A=e^{-1}
§1.8.1 定義
對象$ Pが射$ f:A \to Cと射$ g:B \to Cの引き戾しであるとは $ f \circ g'=g \circ f'なる射$ f':P \to Bと射$ g':P \to Aが存在する
$ f \circ i=g \circ jなる射$ i:X \to Aと射$ j:X \to Bが在れば、$ i=g' \circ kかつ$ j=f' \circ kなる射$ kがただ 1 つ存在する
可換圖式$ P\xrightarrow{g'}A\xrightarrow{f}C\xleftarrow{g}B\xleftarrow{f'}P pullback square (引き戾し正方圖式)
cartesian square (カルテシアン正方圖式)
射$ f'は「$ gに從った$ fの pullback (引き戾し、inverse image、逆像)」と呼ぶ 射$ g'は「$ fに從った$ gの引き戾し」と呼ぶ §1.8.2 例
集合$ A,$ B,$ C,$ f^{-1}(A) $ A \subseteq Cとする
$ Aの$ fによる inverse image (原像、逆像)$ f^{-1}(A):=\{b|f(b)\in A\}
$ f^{-1}(A) \subseteq Aかつ$ f^{-1}(A) \subseteq Bである
函數$ f:B\to C,$ f|_{f^{-1}(A)}:f^{-1}(A)\to A,$ \subseteq:f^{-1}(A)\hookrightarrow B,$ \subseteq:A\hookrightarrow C
$ fの$ Sへの restriction (制限寫像) を$ f|_Sと書く
inclusion function (包含寫像) を$ \subseteqと書く
「圖式が引き戾しである」といふ言葉の嚴密な說明は §1.9 でやる 確かめよ
§1.8.3 例
集合$ A,B \subseteq C
包含寫像$ A \cap B \hookrightarrow A \hookrightarrow Cと$ A \cap B \hookrightarrow B \hookrightarrow Cによる正方圖式は引き戾しになる 包含寫像を餘域における函數として見ると恆等寫像であるから、圖式は可換である
圖式を可換にする寫像$ i:X\to A,$ j:X\to Bが在るとすると、$ \exist k_{:X\to A\cap B}
$ \because$ i,jの餘域が$ {\rm cod}(i)\cap{\rm cod}(j)の部分集合になるやうに$ i,jを制限すればよい
可換圖式なので$ \subseteq_A \circ i(x_{\in X})=\subseteq_B\circ j(x)であり$ i(x),j(x)_{\in A \cap B} $ k,k':X \to A \cap Bとすると$ k=k'
$ \because$ k(x) \neq k'(x)とすると$ \subseteq_A \circ \subseteq_{A \cap B \to A} \circ k' \neq \subseteq_B \circ \subseteq_{A \cap B \to B} \circ k'となり圖式が可換でなくなる
§1.8.4 例
寫像$ f:A \to C,$ g:B \to C
$ P:=\{(a,b)|a \in A,b \in B,f(a)=g(b)\}と定義すれば、これは寫像$ f,gの引き戾しである $ A\times B=\{(a,b)|a\in A,b\in B\}なので$ P\subseteq A\times B
引き戾しにおける projection (射影) は$ f'((a,b)):P \to B=b,$ g'((a,b)):P \to A=a $ f \circ g'((a,b))=f(a),$ g \circ f'((a,b))=g(b),$ Pの定義より圖式は可換
圖式を可換にする$ i:X\to A,$ j:X\to Bが在るとする
$ i=g'\circ k,$ j=f'\circ kとなる$ \exist k_{:X\to P}
$ \because$ k(x \in X)=(i(x),j(x))と定義すればよい (積の時と同じ)
可換圖式なので$ f \circ i(x)=g \circ j(x)であり$ (i(x),j(x)) \in P $ k,k':X \to Pが圖式を可換にするならば$ k=k'
$ \because$ k'(x) \neq k(x)とすると$ g' \circ k'(x) \neq i(x) \vee f' \circ k'(x) \neq j(x)であり圖式が可換でなくなる
$ (A \times B) \to A \to Cと$ (A \times B) \to B \to Cの等化子ですね §1.8.5 例
$ \exist! P \to 1であるから$ !_A \circ g=!_B \circ fであり圖式は可換
圖式を可換にする$ i:X \to A$ j:X \to Bが在れば$ \exist! k:X \to A \times B
$ \because積の定義
$ f:A \times B \to B$ g:A \times B \to Aは積の圖式における射影に他ならない
§1.8.6 例
$ Xが$ f:A \to B$ g:A \to Bの引き戾しであるなら、引き戾しの射影$ e:X \to Aは$ f,gの等化子である §1.8.7 練習問題
pullback lemma (引き戾しの補題)。書籍掲載の圖式を考へよ
§1.2.4 より圖式全體は可換
圖式を書いて
圖式が可換であり、外側の四角と內側の右の四角が引き戾しであるなら、內側の左の四角も引き戾しである事を示せ 圖式を書いて
ヒント : §1.8.4
$ (A \times B) \to A \to Cと$ (A \times B) \to B \to Cとの等化子を書きませう 引き戾しの雙對である pushout (押し出し) について。集合の圈$ \bf Setにおいて$ f:A\to B,$ g:A\to Cの押し出しは disjoint union (非交和、直和) $ B+Cによって與へられる。また$ \iota_1(f(x\in A))は$ \iota_2(g(x))の餘等化子である。この事を示せ $ Pが$ f:C \to Aと$ g:C \to Bの押し出しであるとは $ g' \circ f=f' \circ gなる$ f':B \to Pと$ g':A \to Pが存在する
$ i \circ f=j \circ gなる$ i:A \to Xと$ j:B \to Xが在れば、$ i=k \circ g'かつ$ j=k \circ f'なる$ kがただ 1 つ存在する
集合の直和$ A+Bとは、直和を成すそれぞれの集合に一意な番號を振れた時に$ A+B=\{(a,1)|a\in A \}\cap\{(b,2)|b\in B\}で定義できる
集合$ A,$ B,$ C,$ B+C/\simと寫像$ f:A\to B,$ g:A\to C,$ f':C\to(B+C/\sim),$ g':B\to(B+C/\sim)から成る圖式を考へる。但し$ B+C上の同値關係$ \simを$ f'\circ g(a)\sim g'\circ f(a)で定める。$ B+C/\simが$ f,$ gの押し出しである事を示す 圖式が可換である事を示す
同じ型の可換圖式を作る$ i:A\to P,$ j:B\to Pが在れば、寫像$ k:(A+B)\to Pが在る事を示す 寫像$ kが$ A+Bから$ Pへの寫像として唯一である事を示す
$ A \to B \to (B+C)と$ A \to C \to (B+C)との餘等化子ですね、でもよい limit
§1.9.1 定義
$ \bf D內の全ての對象$ D_iに對して、書籍掲載の圖式を可換にする射$ f_i:X \to D_iが在る
圖式に射$ g:D_i \to D_jが在る場合、$ g \circ f_i=f_jとなる
射$ f_iの集まり$ \{f_i:X\to D_i\}を以て錐 (cone)と呼ぶ §1.9.2 定義
$ \bf Dに他の錐 (cone)$ \{f'_i:X'\to D_i\}が在ったとする 射$ \exist! k_{:X'\to X}であり、$ f'_i=f_i\circ k
1.9.3 例
圈$ \bf C內の對象$ A,$ Bから成る圖式$ \bf Dを考へる 圖式內には$ Aと$ Bの閒には射が無い
2 つの射$ f:X \to Aと$ g: X \to Bが在れば、$ (X,\{f,g\})は$ \mathbf Dの錐 (cone) §1.9.4 例
圈$ \bf Cにおいて空の圖式$ \bf Dの錐 (cone)は、$ \bf Cの任意の對象 例示は定義ではないので、極限 (圈)の定義に終對象を使ってゐても、一例である事は言へますne-sachirou.icon 別の定義の仕方が無いとは主張してゐず、定義は同値であれば場合によって使ひ易いものを選ぶのがいいと思ふ
§1.9.5 例
對象$ A,$ B,$ Cと射$ f:A\to C,$ g:B\to Cから成る圖式$ \bf Dを考へる
$ \bf Dの錐 (cone)は、對象$ Pと可換な射$ g':P\to A,$ f':P\to B,$ h:P\to C 可換性より$ hは合成射$ h=f \circ g'=g \circ f'に他ならないから、$ hは考へなくてもよい
§1.9.6 定義
圈$ \bf C內の圖式$ \bf Dの cocone (餘錐) とは $ \bf D內の全ての對象$ D_iに對して、書籍掲載の圖式を可換にする射$ f_i:D_i\to Xが在る
圖式に射$ g:D_i \to D_jが在る場合、$ f_i \circ g=f_jとなる
射$ f_iの集まり$ \{f_i:D_i\to X\}を以て餘錐と呼ぶ 餘錐$ \{f_i:D_i\to X\}が圖式 $ \bf Dの餘極限であるとは $ \bf Dに他の錐 (cone)$ \{f'_i:D_i\to X'\}が在ったとする 射$ \exist! k_{:X\to X'}であり、$ f'_i=k\circ f_i
圖式$ \mathbf Dへの餘錐全體の圈の始對象 全ての對象に恆等射$ \rm idしか無い圈、discrete category (離散圈) どの圖式が極限 (圈)を持つかといふ事から、その圈についてよく知る事ができる あまりにも自明過ぎて譯が正しいのか不安ne-sachirou.icon
§1.9.7で示す
§2.1.9 注意を見よ
§1.9.7 定理
limit theorem
$ \bf Dを圈$ \bf Cの圖式とし、$ Vを$ \bf Dの頂點 (對象) 集合、$ Eを$ \bf Dの辺 (射) の集合とする $ \bf Cの中に$ \bf Dと同じ型を持つ對象と射の集まりを見附けられれば、その對象と射を$ \bf Dで添字附けるといふ
或る圖式$ \bf Dを決めて、$ \bf Cの中で$ \bf Dを考へた場合$ \bf Dの全ての對象の組が積 (圈)を持ち$ \bf Dの全ての射の組が等化子を持つならば、$ \bf Dは極限 (圈)を持つ 證明の槪略
圖式$ \mathbf Dの全ての對象の積 (圈)$ \prod_{I \in V}D_Iがこの極限 (圈)によささうである しかしこれだけでは充分でない。といふのも積 (圈)からの射と圖式の辺$ D_eとの三角形は可換であるとは限らないから 圖式$ \mathbf Dにおいて餘域になりうる全ての對象の積 (圈)$ \prod_{(e_{:I\to J})\in E}D_Jを作る 邊$ D_e:D_I \to D_Jを使って、$ \prod_{I \in V}D_Iから$ D_Jへの射を 2 通りに作れる
1 つは$ \pi_J。但し$ \pi_J:\prod_{I \in V}D_I \to D_J
もう 1 つは$ D_e \circ \pi_I。但し$ \pi_I:\prod_{I \in V}D_I \to D_I
$ \prod_{(e_{:I\to J}) \in E}D_Jは積 (圈)なので、上記 2 種の射は$ \prod_{I \in V}D_Iから$ \prod_{(e_{:I\to J}) \in E}D_Jへの仲介射を導く $ \prod_{I \in V}D_Iのような對象$ Xで、$ Xから$ D_Jへの射と、$ Xから$ D_eを通って$ D_Jに至る合成射とが等しくなれば、この三角形は可換となり、$ Xは極限 (圈)と言へるのであった §1.9.8 練習問題
§1.9.7を證明せよ
書籍参照…
§1.9.9 例
lambda-calculus (λ計算) のモデルと、その基礎である再歸的な等式$ D \simeq D \to Dを定義する 直感的には Scott の領域$ D_\inftyは、大きくなってゆく領域の無限の連なりとして定義される
小さい領域から大きい領域への emdedding、大きい領域から小さい領域への projection、$ D_\inftyはその「極限 (圈)」 $ Dは最小元を持つ
$ Dの任意の有向部分集合が上限 (上界の最小元) を持つ
圈論的に言へば
各領域は對象
embedding と projection は射
詳しくは§3.4 再歸的な領域方程式でやる
不動點意味論だと思ふんですけど、領域理論わからへんので解說は飛ばしますねne-sachirou.icon §1.9.10 練習問題
圖式$ Dとして$ f,g:A \to Bを考へる。この極限 (圈)は等化子である事を示せ $ Xがこの圖式の極限 (圈)であるとして、$ h:X \to A,$ i:X \to Bと置く $ Xは極限 (圈)なので$ f \circ h=g \circ h=i 下界の定義から、下界は圖式の全ての對象へ射を持つ
上界の定義から、圖式の全ての對象は上界への射を持つ
まず集合の圈$ \mathbf{Set}で極限を構成する $ \bf Setでの對象$ A,Bの積 (圈)は、集合の直積$ A \times B=\{(a,b)|a \in A,b \in B \} $ \mathbf{Set}での射$ f,g:A \to Bの等化子は、$ X=\{x|x \in A,f(x)=g(x) \}とした時の$ Xの恆等寫像 積 (圈)$ \prod_{I \in V}D_Iは、圖式中の全ての集合の直積 積 (圈)$ \prod_{(e_{:I\to J})\in E}D_Jは、圖式中で餘域と成りうる全ての集合の直積 射$ \pi_Iは、$ \prod_{I \in V}D_Iから$ D_Iの要素を選ぶ寫像$ \pi_I(…,d_I(\in D_I)…)=d_I。射$ \pi_Jも同じ
射$ \pi_eは、$ \prod_{(e_{:I\to J})\in E}D_Jから$ D_Jの要素を選ぶ寫像$ \pi_e(…,d_J(\in D_J),…)=d_J
仲介射$ pは、$ \prod_{I \in V}D_Iから$ \prod_{(e_{:I\to J})\in E}D_Jに含まれる集合の要素を選ぶ寫像 仲介射$ qは、$ pに加えて$ D_Iの要素に$ D_eを作用させる寫像
$ p,qの等化子$ h:X \to \prod_{I \in V}D_Iは、$ Xを圖式の全ての集合で但し圖式中の全ての寫像についてそれを恆等な部分に制限した部分集合の直積として、その恆等寫像 射$ f_Iは、$ Xから$ D_Iの要素を選ぶ寫像
§1.9.7 定理よりこの$ \{f_I:X\to D_I\}が極限 (圈) $ \bf Poset の對象は半順序集合、射は單調函數 $ \bf Posetでの對象$ A,Bの積 (圈)は、$ (a,b)\le(a',b')を$ (a\le a')\wedge(b\le b')と定義した時の$ \{(a,b)|a\in A,b\in B\} 射$ f:(A \times B)\to Aは、$ f((a,b))=a
$ \bf Posetでの射$ f,g:A\to Bの等化子は、$ X=\{x|x\in A,f(x)=g(x)\}とした時の$ Xの恆等寫像 あとは$ \bf Setと同じ
§1.9.7 定理の雙對を用いて、圈$ \bf Setでの餘極限を構成せよ 定理の雙對はまた定理である
圖式$ \bf Dにおいて對象と射が常に餘積と餘等化子を持てば、$ \bf Dは餘極限を持つ $ \bf Setでの對象$ A,Bの餘積は、集合の直和$ A+B=\{(a,1)|a\in A\}\cap\{(b,2)|b\in B\}。但し番號は圖式中の全ての集合に對して一意 射$ f:A \to A+Bは、$ f(a)=(a,1)
$ \bf Setでの射$ f,g:A\to B餘等化子は、$ B上の同値關係$ \simを$ f(a\in A)\sim g(a)と定義した時の同値類$ B/\simへの$ Bからの自然な寫像 和$ \sum_{I \in V}D_Iを作る
和$ \sum_{(e_{:J \to I})\in E}D_Jを作る
あとはひとつ上の練習問題を雙對にして、仲介射と餘等化子を構成してくれ limit までに出てきた槪念をざっくりおさらいしてみると
terminal object とは、すべてのオブジェクト $ A に對して唯一の射 $ f: A \to 1 が存在するようなオブジェクト $ 1 のことであった。
product とは、2つのオブジェクト $ A と $ B があり、$ A \leftarrow A \times B \rightarrow B といふ圖がある時に、すべてのオブジェクト $ C、射 $ f: C \to A, g: C \to B に對して唯一の射 $ \langle f, g \rangle: C \to A \times B が存在するやうなオブジェクト $ A \times B のことであった。
equalizer とは、2つのオブジェクト$ A と $ B があり、2つの射 $ f, g: A \to B があり、 $ X \overset{e}{\to} A \overset{f}{\underset{g}{\rightrightarrows}} B のようになっているときに、すべてのオブジェクト $ X'、射 $ e': X' \to A に對して $ f \circ e' = g \circ e' を滿たすならば、唯一の射 $ k: X' \to X が存在して $ e \circ k = e' を滿たすというものだった。
これらの定義は、ぼんやり眺めていると驚くほど似ている。そして pullback も、似たような定義となっている。つまり、「最初に何らかのオブジェクトと射があって (これを圖式$ Fとする)、あるオブジェクト $ X が$ F の各オブジェクトへの射があって圖式を可換にしているときに、他のすべてのオブジェクト $ X' と $ X' から $ F の各オブジェクトへの射があって圖式を可換にするならば、 $ k: X' \to X (mediating arrow) が唯一存在して、圖式を可換にする」という構造である。
この「最初の圖式」「とあるオブジェクト $ Xと圖式のオブジェクトへの射」「他のオブジェクト$ X'と圖式のオブジェクトへの射があれば可換にする」「ならば $ X' \to X が唯一存在して圖式を可換にする」これらを嚴密に定義したものが limit である。
「圈$ \bf C の中の圖式」の定義は圈の中の (有限個または無限個の) オブジェクトを選び、それらの閒の射を選び、圖に書いたもの、で良いのだが、より形式的には添字圈 (index category) J から C への函手として定義される。添字圈といふのはオブジェクトの名前は何でもよくて (つまりただの數字でよくて)、それらの閒の射に注目するために用いられる。添字圈から $ \bf C への函手を使ふことで、圈$ \bf C の中からオブジェクトと射を選ぶことになっているのだ。添字圈からの函手という言葉に混乱したときは、單に圈からオブジェクトと射を選んだだけと思ひ直せば良い。 集合$ Aに對して全域函數 $ \{ x \} \to A が $ a \in A と對應するのと似ている 圖式のオブジェクトへの射があり可換にするあたりが cone に對應
ある cone が、他のすべての cone に對してその對象からの唯一の mediating arrow が存在するというのが limit
limit は、(當初の狙い通り) terminal object や product、equalizer などの一般化になっているはずである。それは、最初に定義した添字圈がどのような形になっているかで具體化される。
なにも對象も射もない圈から limit を構成すると、terminal object になる $ \cdot \quad \cdot のような離散圈 (射が恆等射しかない圈) から limit を構成すると product になる $ A \times B を定義する時に、$ A \to B の存在は不要だった
$ \cdot \to \cdot \leftarrow \cdot のような圈から limit を構成すると pullback になる $ \cdot \rightrightarrows \cdot のような圈から limit を構成すると、equalizer になる limit の定義の dual をとると、colimit を定義できる。これは initial object、coproduct、pushout、coequalizer の一般化となっている。
pullback に對應する添字圈と pushout に對應する添字圈は別のものであることに注意したい。colimit は添字圈の射までは逆にしないからである。
§1.10 冪
圈で計算理論を行ふ時に冪は currying (curry 化) の說明を與へる
2 引數函數を 1 引數函數の合成として扱ふ
$ A,Bを集合とすると、$ Aから$ Bへの寫像全體の集まり$ B^A=\{f:A\to B\}も集合である つまり$ B^A=\{f|{\rm dom}(f)=A,{\rm cod}(f)=B\}
冪集合$ 2^Aは$ \{0,1\}^Aとも書ける (みなせる) hom set (hom 集合)
これは圈で考へると、對象$ A,B\in|{\bf C}|について、$ {\bf C}(A,B)を表現する對象$ B^A\in |{\bf C}|が在る事に當たる ただこの觀察は全ての圈で成り立つわけではない。例へばmonoid の圈$ \bf Monではこの譬喩は成り立たない 下記
この$ B^Aを集合の要素によらず、射で特徵づけたい $ {\rm eval}((f,a))=f(a)で定義される寫像$ {\rm eval}:(B^A\times A)\to Bを考へる
$ f:A\to Bで$ a\in Aなので$ f(a)\in Bである
この$ \rm evalを射$ g:C\times A\to Bの中で普遍 (圈論)性を持つものとすれば、$ B^Aを圈論的に特徵づけられるだらう 射$ gに對して次の射$ {\rm curry}(g):C\to B^Aが一意に存在する事を見る
當然$ {\rm curry}(g)\times{\rm id}_A:(C\times A)\to(B^A\times A)である
§1.5.3 定義で積 (圈)の閒の射を定義したやうに、$ {\rm curry}(g)\times{\rm id}_Aは$ (c,a)を引數として$ ({\rm curry}(g)(c),a)を返す射 $ {\rm eval}\circ({\rm curry}(g)\times{\rm id}_A)=gでなければならない
$ c \in Cから$ B^Aへの寫像は、$ gの第一引數に$ cを部分適用したものだと見做せる
$ gを$ c \in Cについて curry 化し部分適用したものを$ g_cと書く事にしやう。つまり$ g_c(a)=g(c,a)
curry 化は既知のものとしてある
$ {\rm curry}(g)こそ正にこれを行ふものだ。つまり$ {\rm curry}(g)(c)=g_cとすると
$ (c,a) \in C \times Aについて
確かに$ ({\rm eval}\circ({\rm curry}(g)\times{\rm id}_A))(c,a)={\rm eval}({\rm curry}(g)(c),a)={\rm eval}(g_c,a)=g_c(a)=g(c,a)
また$ g_cは圖式を可換にする唯一の寫像である
$ {\rm eval}({\rm curry}(g)(c),a)=g(c,a)なので、$ ({\rm curry}(g)(c))(a)=g(c,a)である
つまり$ {\rm curry}(g)(c)は$ g_cといふ事
對象は、monoid。臺集合と演算の組$ (A,*),$ (B,*) 射は、monoid の演算を保存する寫像。$ f:A \to Bにおいて$ f(a*a')=f(b)*f(b') 積 (圈)は、臺集合の直積に元の monoid から自然な演算を入れたもの。$ (A \times B,*)は$ (a,b)*(a',b')=(a*a',b*b') $ \bf Monの Hom は monoid 構造を持たないし、冪對象も無いといふ話かne-sachirou.icon §1.10.1 定義
圈$ \bf Cの全ての對象の組$ A,Bが積 (圈)を持つ時、對象$ B^Aが exponential object (冪對象) であるとは 射$ {\rm eval}_{AB}:(B^A\times A)\to B(評價射) が在る
射$ g:(C \times A) \to Bが在れば、$ \exist!{\rm curry}(g)_{:C\to B^A}であり、$ {\rm eval}_{AB}\circ({\rm curry}(g)\times{\rm id}_A)=g
圈$ \bf Cが全ての對象の組$ A,Bについて冪對象$ B^Aを持てば、$ \mathbf Cは冪對象を持つと言ふ $ {\rm eval}_{AB}を evaluation (評價)、$ {\rm curry}(g)を$ gの transpose (轉置) とも呼ぶ
§1.10.2 定義
§1.5.5 定義のやり方で
$ X,Yが在れば$ X^Yも$ Y^Xも作れる
§3.1 デカルト閉圈で詳しく出て來る
§1.10.3 例
§1.10.4 例
§3.4.6まで待ちませう
§1.10.5 練習問題
Cartesian 閉ではない圈の例には以下のようなものが挙げられる。 固定された體上の線形空閒全體の成す圈や有限次元 vector 空閒の圈はともに Cartesian 閉ではない。これらの圈は「直和」と呼ばれる直積は持つけれども、直積函手の右隨伴が存在しない (これらの圈は對稱 monoidal 閉圈ではある。線形空閒の閒の線形寫像全體の成す集合は再び 線形空閒をなすといふ意味で閉であり、直積の代はりに tensor 積を考えれば Hom 集合の閒に同樣の同型が存在する)。 2 圈$ A,B,{\rm id}_A,{\rm id}_B,f:A\to Bは Cartesian 閉…あれー?
積 (圈)$ A \times A=A,$ B \times B=B,$ A\times B=B\times A=A 冪$ A^A=B$ B^B=B$ B^A=B$ A^B=A
$ A=0,$ B=1 とすると $ 0^0 = 1 ですね
$ A = \bot,$ B = \top とするとさうですねという氣持ちになってきた
助けてne-sachirou.icon
圈$ {\bf Set}\times{\bf Set}の冪對象は集合要素を考へると$ \bf Setの冪對象と同じである。調べよ $ {\bf Set}\times{\bf Set}の對象は集合の直積$ A\times B、射$ f:(A\times B)\to(C\times D)は$ g:A\to C,$ h:B\to Dを用意して$ f((a,b))=(g(a),h(b))
$ {\bf Set}\times{\bf Set}の積 (圈)は、$ (A\times B)\times(C\times D)=\{((a,b),(c,d))|(a,b)\in A\times B,(c,d)\in C\times D\} $ (C \times D)^{(A \times B)}は$ {\bf Set}\times{\bf Set}(A \times B,C \times D)と成る事を示す
節の冒頭と同じ構成を地道に書き下す事になる
圈$ \mathbf{Set}^\toの冪對象を構成せよ $ {\bf Set}^\toの定義
對象は、集合の圈$ \bf Setの射$ f:A\to B,$ f':A'\to B'全體の集まり 射は、$ \bf Setの 2 つの射$ a:A\to A',$ b:B\to B'で$ f'\circ a=b\circ fであるものを使ひ$ (a,b):f\to f'と定義する
合成射は$ (a',b')\circ(a,b)=(a'\circ a,b'\circ b)と定義する
arrow category の一例
助けて…ne-sachirou.icon
$ f \to f'の集まりを考へてこれを$ {\bf Set}^\toで探し、冪對象になる事を確かめる、のか?ne-sachirou.icon
難しいのでGoldblatt [40, p.88]を見よ
https://gyazo.com/b2fbf0bc1ea7e3bc900378ec6a59a2e5
$ g^f:\{(h,k):f\to g\}\to D^B,$ {\rm eval}_{fg}:g^f\times f\to g=(u,v) とする
$ h:A\to C,$ k:B\to D,$ g^f(h,k)=k とする
$ v:D^B\times B\to D={\rm eval}_{BD}、$ u:\{(h,k):f\to g\}\times A\to C=((h,k),a)\Rarr h(a)~(a\in A) により定義する。
$ {\rm eval}_{BD}\big((g^f\times f)((h,k),a)\big)={\rm eval}_{BD}(k,f(a))=k(f(a))
$ g\big(u((h,k),a)\big) = g(h(a))
$ k\circ f=g\circ h より上の 2 つは等しくなり、$ v\circ(g^f\times f)=g\circ u が示された。
$ {\rm curry}({\rm eval}_{AB})={\rm id}_{B^A}を示せ
冪對象の定義の圖式の、$ Cが$ B^Aである時の事 可換性$ {\rm eval}_{AB}\circ({\rm curry}({\rm eval}_{AB})\times{\rm id}_A)={\rm eval}_{AB}が成り立つ
仮に$ {\rm curry}({\rm eval}_{AB})={\rm id}_{B^A}であるとしたら、$ {\rm id}_{B^A}\times{\rm id}_Aは$ {\rm id}_{B^A\times A}であるから$ {\rm eval}_{AB}\circ({\rm id}_{B^A}\times{\rm id}_A)={\rm eval}_{AB}\circ{\rm id}_{B^A\times A}={\rm eval}_{AB}
$ B^Aは冪對象であるから、このやうな$ {\rm curry}({\rm eval}_{AB})は$ {\rm id}_{B^A}しか存在しない 評價射は$ {\rm eval}_{(A\times A')B}:B^{A\times A'}\times(A\times A')\to Bと$ {\rm eval}_{A'(B^A)}:(B^A)^{A'}\times A'\to B^Aと$ {\rm eval}_{AB}:B^A\times A\to B
積 (圈)と合成射を使って$ ((B^A)^{A'}\times A')\times A\to B^A\times A\to Bを作れる。冪の圖式から$ (B^A)^{A'}\times A'\times A\to B^{A\times A'}\times(A\times A')が一意に存在し、$ (B^A)^{A'}\to B^{A\times A'}も一意に存在する ここで逆方向の射$ B^{A \times A'} \rightarrow (B^A)^{A'}を作りたい…ne-sachirou.icon
冪對象自身も當然冪の圖式に當て嵌まり、恆等射と合成射は同じ圖式で冪になる。ならば兩者は等しくなければならない Steve Awodey「圈論」2015, p164https://gyazo.com/27c81779760ec6b2d2120115ca651f59
Steve Awodey「圈論」2015, p329https://gyazo.com/66709977f3d4c3cc84a5205a7fa26655
竹內外史「層・圈・トポス」1978, p89https://gyazo.com/16a5336b404cc2c4734b1a9ab8328d21
Hom の同型を使へるとめっちゃ樂だなーne-sachirou.icon
$ \cal Pを powerset operator (冪集合演算子) とし、集合$ Sに對してその全ての部分集合を取り$ {\cal P}(S)=\{T|T \subseteq S\}と定義する。半順序$ ({\cal P}(S),\subseteq)は Cartesian 閉圈 (CCC)である事を示せ 順序圈としてのHeyting 代數における指數對象$ Z^Yは相對擬補元$ Y \rightarrow Zに他ならない。 相對擬補元とは$ {\rm max}\{X|X\wedge Y\le Z\}
推移律$ T \subseteq Uかつ$ U \subseteq Vならば$ T \subseteq V 反對稱律$ T \subseteq Uかつ$ U \subseteq Tならば$ T=U 素朴な集合論を仮定してください…
積 (圈)$ T \times Uは、結び$ T \cap U $ T \cap U \subseteq T,Uであり、$ T \cap Uはそのやうなものの中で最大
$ \mathcal{P}(S)は空集合$ \phiを含むので結びは必ず存在する
冪對象$ U^Tは、$ \lbrace X|X \cap T \subseteq U \rbraceの上限 評價射$ {\rm eval}_{TU}:U^T\cap T\subseteq Uは常に存在する
對象$ Xと射$ g:X \cap T \subseteq Uが在るとする
射$ {\rm curry}(g):X\subseteq U^Tが存在ししかもただ一つである事を示す
$ gと$ U^Tの定義より明らかに存在する
半順序の順序であるから存在するならばただ一つである 射$ {\rm curry}(g)\times{\rm id}_T:X\cap T\subseteq U^T\cap Tが存在ししかもただ一つである事を示す
$ A \subseteq Bであるならば$ A \cap C \subseteq B \cap Cであるが故に、$ {\rm curry}(g)が存在するならばこれも存在する
半順序の順序であるから存在するならばただ一つである 半順序の合成射はただ一通りであるから$ {\rm eval}_{TU}\circ({\rm curry}(g)\times{\rm id}_T)=(X\cap T)\subseteq(U^T\cap T)\subseteq U=gであり、可換 $ Sを propositional logic (古典論理、古典命題論理) の文であるとせよ。文$ p,qについて$ pから$ qを導出できる時に$ p \le qとすれば$ (S,\le)は半順序である。積 (圈)を conjunction (結び) とし、冪對象$ q^pを$ pは$ qを含意する事とすれば、これらは Cartesian 閉圈 (CCC)を成す事を示せ 命題$ pがどんな眞理値を持っても$ p\to{\rm True}は成り立つ
$ (p \wedge q \rightarrow p)=p,$ (p \wedge q \rightarrow q)=q
若し$ (r \rightarrow p) \wedge (r \rightarrow q)ならば$ r \rightarrow (p \wedge q)
評價射$ {\rm eval}_{pq}:((p\rightarrow q)\wedge p)\rightarrow qは成り立つ
命題$ rが在り$ r \wedge p \rightarrow qが成り立つとする
$ {\rm curry}:r\to(p\to q)は成り立つ
$ {\rm curry}\times{\rm id}:r\wedge p\to(p\to q)\wedge pは成り立つ
この場合命題論理の意味論を仮定し、眞理値表に當て嵌めてしまってもよい
古典論理なので$ aが僞ならば$ a \rightarrow bは眞 §1.1.15 例で見た圈$ \mathbf{FPL}を higher-order function (高階函數) に擴張せよ $ \mathbf{FPL}とは
對象$ \rm Int,$ \rm Real,$ \rm Bool,$ \rm Unit
射$ {\rm iszero}:{\rm Int}\to{\rm Bool},$ {\rm not}:{\rm Bool}\to{\rm Bool},$ {\rm succ}_{\rm Int}:{\rm Int}\to{\rm Int},$ {\rm succ}_{\rm Real}:{\rm Real}\to{\rm Real},$ {\rm toReal}:{\rm Int}\to{\rm Real}
$ {\rm Unit}からの射である定數$ {\rm zero}:{\rm Int},$ {\rm true}:{\rm Bool},$ {\rm false}:{\rm Bool},$ {\rm unit}:{\rm Unit}
$ {\rm add}:{\rm Int}\to{\rm Int}\to{\rm Int}とか定義すればいいかな
$ ({\rm Int}\times{\rm Int})\to{\rm Int}でもあり、$ ({\rm Int}^{\rm Int}\times{\rm Int}\to{\rm Int})\circ({\rm Int}\times{\rm Int}\to{\rm Int}^{\rm Int}\times{\rm Int})でもあるところの
對象$ {\rm Int}\times{\rm Int},$ {\rm Int}^{\rm Int},$ {\rm Int}^{\rm Int}\times{\rm Int}を足す必要が有ります